package pojo

import "fmt"

type MyStrongInt struct {
	Value int
}

type StrongHeap struct {
	heapSize    int
	Array       []*MyStrongInt
	indexMap    map[*MyStrongInt]int
	compareFunc func(int, int) bool
}

func NewStrongHeap(fus ...func(int, int) bool) StrongHeap {
	fuc := func(i int, i2 int) bool {
		return i > i2
		//大于是升序
	}
	for _, fu := range fus {
		fuc = fu
	}
	return StrongHeap{
		heapSize:    0,
		Array:       make([]*MyStrongInt, 10),
		indexMap:    make(map[*MyStrongInt]int),
		compareFunc: fuc,
	}
}

func (h *StrongHeap) GetSize() int {
	return h.heapSize
}
func (h *StrongHeap) IsEmpty() bool {
	return h.heapSize == 0
}
func (h *StrongHeap) swap(i, j int) {
	iIndexValue := h.Array[i]
	jIndexValue := h.Array[j]
	i2 := h.indexMap[iIndexValue]
	j2 := h.indexMap[jIndexValue]
	h.indexMap[jIndexValue] = i2
	h.indexMap[iIndexValue] = j2
	h.Array[i], h.Array[j] = h.Array[j], h.Array[i]
}
func (h *StrongHeap) HeapUp(index int) {
	if index < 0 {
		return
	}
	father := (index - 1) / 2
	for father >= 0 {
		if h.compareFunc(h.Array[father].Value, h.Array[index].Value) {
			h.swap(father, index)
			index = father
			father = (index - 1) / 2
		} else {
			return
		}
	}
}
func (h *StrongHeap) HeapDown(index int) {
	if index < 0 {
		return
	}
	leftChild := index*2 + 1

	for leftChild < h.heapSize {
		min := leftChild
		if h.compareFunc(h.Array[leftChild].Value, h.Array[leftChild+1].Value) && (leftChild+1) < h.heapSize {
			min = leftChild + 1
		}
		if h.compareFunc(h.Array[min].Value, h.Array[index].Value) {
			min = index
		}

		if min == index {
			break
		}

		h.swap(min, index)
		index = min
		leftChild = index*2 + 1
	}

}

func (h *StrongHeap) Add(Value int) {
	IntBody := &MyStrongInt{Value: Value}
	h.Array[h.heapSize] = IntBody
	h.indexMap[IntBody] = h.heapSize
	h.HeapUp(h.heapSize)
	h.heapSize++

}
func (h *StrongHeap) Peek() int {
	return h.Array[0].Value
}

func (h *StrongHeap) Remove(obj *MyStrongInt) {
	repalce := h.Array[h.heapSize-1]
	index := h.indexMap[obj]
	delete(h.indexMap, obj)
	h.heapSize--

	if obj != repalce {
		h.Array[index] = repalce
		h.indexMap[repalce] = index
		h.Resign(repalce)
	}
}

func (h *StrongHeap) Poll() int {
	min := h.Array[0].Value
	h.swap(h.heapSize-1, 0)
	delete(h.indexMap, h.Array[h.heapSize-1])
	h.heapSize--
	h.HeapDown(0)

	return min
}

func (h *StrongHeap) Contains(strongInt *MyStrongInt) bool {
	_, flag := h.indexMap[strongInt]
	return flag
}

func (h *StrongHeap) Resign(strongInt *MyStrongInt) {
	h.HeapUp(h.indexMap[strongInt])
	h.HeapDown(h.indexMap[strongInt])
}

func (h *StrongHeap) Print() {

	for i := 0; i < h.heapSize; i++ {
		fmt.Print(h.Array[i].Value, " ")
	}

	fmt.Println()
	for strongInt, i := range h.indexMap {
		fmt.Print(strongInt.Value, ":", i, " ")
	}
	fmt.Println()
}
